package 动态规划;

import java.util.HashMap;
import java.util.Map;

public class 编辑距离 {

    /**
     * 给定两个单词，判断将word1 转为 word2需要的最短距离
     * @param word1
     * @param word2
     * @return
     */

    private static Map<String, Integer> map = new HashMap<>();
    public int minDistance(String word1, String word2) {
        //递归不行
//        return minDistanceReverse(word1, word2, 0, 0);
        //dp来凑
        int m = word1.length();
        int n = word2.length();
        int[][] dp = new int[m+1][n+1];
        for (int i = 1; i < m + 1; i++) {
            dp[i][0] = i;
        }
        for (int j = 1; j < n + 1; j++) {
            dp[0][j] = j;
        }

        for (int i = 1; i < m+1 ; i++) {
            for (int j = 1; j < n+1; j++) {
                if(word1.charAt(i-1) == word2.charAt(j-1)) {
                    dp[i][j] = dp[i-1][j-1];
                }else {
                    dp[i][j] = threeMin(
                            dp[i][j-1], dp[i-1][j], dp[i-1][j-1]
                    )+1;
                }
            }
        }
        return dp[m][n];
    }

    private int minDistanceReverse(String word1, String word2, int i, int j) {
        String key = i+""+j;
        if(map.get(key)!= null) {
            return map.get(key);
        }
        if(j>=word2.length()) {
            return word1.length() - i;
        }
        if(i>=word1.length()) {
            return word2.length() - j;
        }
        if(word1.charAt(i) == word2.charAt(j)) {
             int result = minDistanceReverse(word1, word2, i+1,j+1);
            map.put(key, result);
            return result;
        }else {
                int result = threeMin(
                        minDistanceReverse(word1, word2, i+1, j)+1,    // 删除
                        minDistanceReverse(word1, word2, i, j+1)+1,   // 插入
                        minDistanceReverse(word1, word2, i+1, j+1)+1  //替换
                );
            map.put(key, result);
            return result;
        }
    }

    private int threeMin(int i, int i1, int i2) {
        return Math.min(i, Math.min(i1,i2));
    }


    public static void main(String[] args) {
        String s1 = "horse";
        String s2 = "ros";
//        System.out.println(minDistance(s1, s2));
        编辑距离 b = new 编辑距离();
        System.out.println(b.minDistance(s1, s2));
    }
}
